<!DOCTYPE HTML PUBLIC "-//IETF//DTD XHTML//EN">
<html>
<head>
<link rel="stylesheet" type="text/css" href="styles.css" media="all"/>
<link rel="icon" type="image/png" href="favicon.ico">

<meta name="description" content="tqDist is a state-of-the-art
software library for computing the triplet and quartet distances
between binary or general trees. A Python module and an R package are
supplied in addition to the executable binaries."/>
<meta name="robots" content="index, follow, noodp"/>
<meta name="google" content="notranslate" />

<title>tqDist</title>
</head>

<body>
<div id=border>
<div id="main">

<img src="tree.jpg" alt="evolutionary tree" style="float:right" width="540">
<h1>tqDist - a triplet and quartet distance library</h1>

<p align="justify" style="width: 650px">
Distance measures between trees are useful for comparing trees in a
systematic manner and several different distance measures have been
proposed. The triplet and quartet distances, for rooted and unrooted
trees, are defined as the number of subsets of three or four leaves,
respectively, where the topologies of the induced sub-trees
differ. These distances can trivially be computed by explicitly
enumerating all sets of three or four leaves and testing if the
topologies are different, but this leads to time complexities at least
of the order <i>n</i><sup>3</sup> or <i>n</i><sup>4</sup> just for
enumerating the sets. The different topologies can be counted
implicitly, however, and this tqDist computes the triplet distance
between rooted trees in <i>O</i>(<i>n</i> log <i>n</i>) time and the
quartet distance between unrooted trees in <i>O</i>(<i>dn</i> log
<i>n</i>) time, where <i>d</i> degree of the tree with the smallest
degree.  </p>

<p style="width: 650px">
<code>tqDist</code> has been implemented in C and C++ to achieve
maximal performance, but bindings to Python and R are also supplied
such that the library easily can be used for scripting. In addition
to this several binary executables are provided.
</p>

<p style="width: 650px">
In the following text we describe how to install <code>tqDist</code>
on Mac OS X, Windows and Linux and illustrate how to use the enclosed
Python module and R package. Finally, we explain how to use the binary
executables.
</p>

<ol>
  <li><a href="#citing_tqdist">Citing tqDist</a></li>
  <li><a href="#files">Files</a></li>
  <li><a href="#build_procedure">Build procedure</a></li>
  <li><a href="#using_the_python_bindings">Using the Python bindings</a></li>
  <li><a href="#using_the_R_bindings">Using the R bindings</a></li>
  <li><a href="#executables">Executables</a></li>
  <!--<ul>
    <li><a href="#build_procedure">triplet_distance</a></li>
    <li><a href="#build_procedure">quartet_distance</a></li>
    <li><a href="#build_procedure">all_pairs_triplet_distance</a></li>
    <li><a href="#build_procedure">all_pairt_quartet_distance</a></li>
  </ul>-->
  <li><a href="#file_format">File format</a></li>
  <li><a href="#literature">Literature</a></li>
  <li><a href="#contact">Contact</a></li>
</ol>

<h2><a id="citing_tqdist">Citing tqDist</a></h2>

<p>
If you use <code>tqDist</code> in your research, please cite it in
the following way:
<ul>
  
  <li>Andreas Sand, Morten K. Holt, Jens Johansen, Gerth
  St&oslash;lting Brodal, Thomas Mailund and Christian N.S. Pedersen;
  <i><a href="http://dx.doi.org/10.1093/bioinformatics/btu157"
  target="blank">tqDist: A Library for Computing the Quartet and
  Triplet<br/> Distances Between Binary or General Trees</a></i>,
  Bioinformatics, 2014, xx(yy), pp. ii-jj, doi:
  10.1093/bioinformatics/btu157.
  
</li>
</ul>
</p>

<p>You can e.g. use <a href="tqDist.bib" target="blank">this BibTex entry</a>.</p>

<p>The datasets used for the performance experiments in this
Applications Note are available for download at <a
 href="data"
target="blank">http://birc.au.dk/~cstorm/software/tqDist/data/</a>.</p>

<h2><a id="files">Files</a></h2>

<ul>
  <li>
  Windows
  <ul>
    <li>Installer: <a href="files/Windows/tqDist-1.0.0-x86_32.exe">tqDist-1.0.0-x86_32.exe</a></li>
    <li>R package: <a href="files/Windows/rtqdist_1.0.tar.gz">rtqdist_1.0.tar.gz</a></li>
    <li>Python module: <a href="files/Windows/pyTQDist_1.0.zip">pyTQDist_1.0.zip</a></li>
  </ul>
  </li>
  <li>Mac OS X
  <ul>
    <li>R package: <a href="files/OSX/rtqdist_1.0.tar.gz">rtqdist_1.0.tar.gz</a></li>
    <li>Python module: <a href="files/OSX/pyTQDist_1.0.zip">pyTQDist_1.0.zip</a></li>
  </ul>
  </li>
  
  <li>Source: <a href="files/tqDist-1.0.0.tar.gz">tqDist-1.0.0.tar.gz</a> or <a href="files/tqDist-1.0.0.zip">tqDist-1.0.0.zip</a></li>
  
</ul>

<h2><a id="build_procedure">Build procedure</a></h2>

<h3><a id="install_binaries_from_source">Install binaries from source</a></h3>

<p>To install tqDist from source on Linux or Mac OS X download <a
href="files/tqDist-1.0.0.tar.gz">tqDist-1.0.0.tar.gz</a> and
execute the following commands in a terminal:</p>

<p>
<div class="snip">
$ cd &lt;path-to-file&gt;<br/>
$ tar -xvf tqDist-1.0.0.tar.gz<br/>
$ cd tqDist-1.0.0/<br/>
$ cmake .<br/>
$ make<br/>
$ make test<br/>
$ make install<br/>
</div>
</p>

<p>This will also install the python module <code>pyTQDist</code>
and/or the R package <code>rtqdist</code> if python and/or R is
installed on your system.</p>

<p>If you do not have permisions to install the package in the default
location, you need to replace the fourth command above by something on
this form:</p>

<p>
<div class="snip">
  $ cmake -DCMAKE_INSTALL_PREFIX=&lt;install prefix&gt; \<br/>
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-DPYTHON_PREFIX=&lt;python libs&gt; -DR_PREFIX=&lt;R libs&gt; .<br/>
</div>
</p>

<p>Finally, if CMake is not installed on your system, you can download
the newest version from <a href="http://cmake.org/"
target="blank">http://cmake.org/</a>.</p>

<h3><a id="mac_os_x">Mac OS X</a></h3>
<p>To install the python module <code>pyTQDist</code> on Mac OS X download <a
href="files/OSX/pyTQDist_1.0.zip">pyTQDist_1.0.zip</a> and execute
the following commands in a terminal:</p>

<p>
<div class="snip">
$ cd &lt;path-to-file&gt;<br/>
$ unzip pyTQDist_1.0.zip <br/>
$ cd pyTQDist_1.0<br/>
$ python setup.py install<br/>
</div>
</p>

<p>To install the R package <code>rtqdist</code> on Mac OS X download
<a href="files/OSX/rtqdist_1.0.tar.gz">rtqdist_1.0.tar.gz</a> and
execute the following commands in a terminal:</p>

<p>
<div class="snip">
$ cd &lt;path-to-file&gt;<br/>
$ R CMD INSTALL rtqdist_1.0.tar.gz<br/>
</div>
</p>  

<h3><a id="windows">Windows</a></h3>

<p>To install the tqDist executables on Windows download and run <a
 href="files/Windows/tqDist-1.0.0-x86_32.exe">tqDist-1.0.0-x86_32.exe</a>.</p>

<p>To install the python module <code>pyTQDist</code> on Windows
download and unzip <a
 href="files/Windows/pyTQDist_1.0.zip">pyTQDist_1.0.zip</a> and run the
following commands in a command window:</p>

<p>
<div class="snip">
$ cd &lt;path-to-pyTQDist_1.0&gt;<br/>
$ python setup.py install<br/>
</div>
</p>

<p>If <code>python</code> is not recognized as a command in your
command prompt, you need to <a href="http://vimeo.com/70504477"
target="blank">add python to your path</a>.</p>


<p>To install the R package <code>rtqdist</code> on Windows download
 <a href="files/Windows/rtqdist_1.0.tar.gz">rtqdist_1.0.tar.gz</a> and
 run the following commands:</p>

<p>
<div class="snip">
$ cd &lt;path-to-file&gt;<br/>
$ R CMD INSTALL --no-multiarch rtqdist_1.0.tar.gz<br/>
</div>
</p>

<p>If <code>R</code> is not recognized as a command in your command prompt, you need
to <a
href="http://cran.r-project.org/bin/windows/base/rw-FAQ.html#Rcmd-is-not-found-in-my-PATH_0021"
target="blank">update your path</a>.</p>

<h3><a id="linux">Linux</a></h3>

<p>To install tqDist on Linux you need to follow the instructions to <a
href="#install_binaries_from_source">install binaries from
source</a>. This will also install the R package and/or the python
module if R and/or python is installed on your system.</p>

<h2><a id="using_the_python_bindings">Using the Python bindings</a></h2>

<p>The following <a href="files/example.zip">example</a> illustrates
how the Python module <code>pyTQDist</code> can be used:</p>

<p>
<div class="snip">
from pyTQDist import *<br/>
<br/>
filename1 = "trees/tree1.new"<br/>
filename2 = "trees/tree2.new"<br/>
<br/>
print "triplet distance:", tripletDistance(filename1, filename2) <br/>
print "quartet distance:", quartetDistance(filename1, filename2) <br/>
<br/>
print allPairsTripletDistance("trees/8trees.new") <br/>
print allPairsQuartetDistance("trees/8trees.new") <br/>
<br/>
print pairsTripletDistance("trees/pairs1.new", "trees/pairs2.new") <br/>
print pairsQuartetDistance("trees/pairs1.new", "trees/pairs2.new")
</div>
</p>

<p><code>tripletDistance</code> and <code>quartetDistance</code> each
take two parameter, which should be filenames pointing to files
containing a single tree in Newick format each. For each tree all
leaves should be labeled and the two trees should share the same set
of leaf labels. The two functions return the distance between the two
trees as a single integer.</p>

<p><code>pairsTripletDistance</code> and
<code>pairsQuartetDistance</code> each take two parameter, which
should be pointing to files containing the same number of trees in
Newick format. The trees on line <i>i</i> in the two files must have
the same set of leaf labels. The two functions return a list of
distances where the <i>i</i>th distance is the pairwise distance
between the two trees on line <i>i</i> in the two files.  </p>

<p><code>allPairsTripletDistance</code> and
<code>allPairsQuartetDistance</code> each take a single parameter,
which should be a filename containing multiple trees in Newick
format. Each tree should be on a seperate line. In each tree all
leaves should be labeled and all trees should share the same set of
leaf labels.  The two functions return a lower triangular as a list of
lists in which entry [<i>i</i>][<i>j</i>] is the pairwise triplet
or quartet distance between the trees on line <i>i</i> and <i>j</i>.

<h2><a id="using_the_R_bindings">Using the R bindings</a></h2>

<p>The following <a href="files/example.zip">example</a> illustrates how the R package
<code>rtqdist</code> can be used:</p>

<p>
<div class="snip">
library("rtqdist") <br/>
<br/>
filename1 = "trees/tree1.new"<br/>
filename2 = "trees/tree2.new"<br/>
<br/>
t = tripletDistance(filename1, filename2) <br/>
q = quartetDistance(filename1, filename2) <br/>
<br/>
allT = allPairsTripletDistance("trees/8trees.new") <br/>
allQ = allPairsQuartetDistance("trees/8trees.new") <br/>
<br/>
pT = pairsTripletDistance("trees/pairs1.new", "trees/pairs2.new") <br/>
pQ = pairsQuartetDistance("trees/pairs1.new", "trees/pairs2.new")
</div>
</p>

<p><code>tripletDistance</code> and <code>quartetDistance</code> each
take two parameter, which should be filenames pointing to files
containing a single tree in Newick format each. For each tree all
leaves should be labeled and the two trees should share the same set
of leaf labels. The two functions return the distance between the two
trees as a single integer.</p>

<p><code>pairsTripletDistance</code> and
<code>pairsQuartetDistance</code> each take two parameter, which
should be pointing to files containing the same number of trees in
Newick format. The trees on line <i>i</i> in the two files must have
the same set of leaf labels. The two functions return a list of
distances where the <i>i</i>th distance is the pairwise distance
between the two trees on line <i>i</i> in the two files.  </p>

<p><code>allPairsTripletDistance</code> and
<code>allPairsQuartetDistance</code> each take a single parameter,
which should be a filename containing multiple trees in Newick
format. Each tree should be on a seperate line. In each tree all
leaves should be labeled and all trees should share the same set of
leaf labels. The two functions return a lower triangular as a list of
lists in which entry [<i>i</i>][<i>j</i>] is the pairwise triplet
or quartet distance between the trees on line <i>i</i> and
<i>j</i>.</p>

<h2><a id="executables">Executables</a></h2>

<p>The following executables are installed with tqDist:</p>

<h3><a id="triplet_dist">triplet_dist</a></h3>

<p>Usage: <code>triplet_dist [-v] &lt;filename1&gt; &lt;filename2&gt;</code></p>

<p>Where <code>&lt;filename1&gt;</code> and
<code>&lt;filename2&gt;</code> point to two files each containing
one tree in Newick format. In both trees all leaves should be
labeled and the two trees should have the same set of leaf labels.
The triplet distance between the two trees will be printed to
stdout.</p>
<p>
If the <code>-v</code> option is used, the following numbers will be reported (in this
order):
<ul>
  <li>The number of leaves in the trees (should be the same for both).</li>
  <li>The number of triplets in the two trees (n choose 3). </li>
  <li>The triplet distance between the two trees. </li>
  <li>The normalized triplet distance between the two trees. </li>
  <li>The number of resolved triplets that agree in the two trees. </li>
  <li>The normalized number of resolved triplets that agree in the two trees. </li>
  <li>The number triplets that are unresolved in both trees. </li>
  <li>The normalized number triplets that are unresolved in both
  trees. </li>
</ul>
</p>

<h3><a id="quartet_dist">quartet_dist</a></h3>

<p>Usage: <code>quartet_dist [-v] &lt;filename1&gt; &lt;filename2&gt;</code></p>

<p>Where: <code>&lt;filename1&gt;</code> and
<code>&lt;filename2&gt;</code> point to two files each containing
one tree in Newick format. In both trees all leaves should be
labeled and the two trees should have the same set of leaf labels.
The quartet distance between the two trees will be printed to
stdout.</p>
<p>
If the <code>-v</code> option is used, the following numbers will be reported (in this
order):
<ul>
  <li>The number of leaves in the trees (should be the same for both).</li>
  <li>The number of quartets in the two trees (n choose 4). </li>
  <li>The quartet distance between the two trees. </li>
  <li>The normalized quartet distance between the two trees. </li>
  <li>The number of resolved quartets that agree in the two trees. </li>
  <li>The normalized number of resolved quartets that agree in the two trees. </li>
  <li>The number of quartets that are unresolved in both trees. </li>
  <li>The normalized number of quartets that are unresolved in
  both trees. </li>
</ul>
</p>

<h3><a id="pairs_triplet_dist">pairs_triplet_dist</a></h3>
<p>Usage: <code>bin/pairs_triplet_dist [-v] &lt;filename1&gt; &lt;filename2&gt; [&lt;output filename&gt;]</code></p>

<p> Where: <code>&lt;filename1&gt;</code> and
<code>&lt;filename2&gt;</code> point to two files each containing the
same number of trees in Newick format. The two trees on line <i>i</i> in the
two files must have the same set of leaf labels.  The output is a list
of numbers, where the <i>i</i>'th number is the triplet distance between the
two trees on line <i>i</i> in the two files. If <code>[output filename]</code> is
specified the output is written to the file pointed to (if the file
already exists the current content is deleted first), otherwise the
output is written to stdout.
</p>

<p>If the <code>-v</code> option is used, the following numbers will be reported for
each pair of trees (in this order):
<ul>
  <li>The number of leaves in the trees (should be the same for both).</li>
  <li>The number of triplets in the two trees (n choose 3). </li>
  <li>The triplet distance between the two trees. </li>
  <li>The normalized triplet distance between the two trees. </li>
  <li>The number of resolved triplets that agree in the two trees. </li>
  <li>The normalized number of resolved triplets that agree in the two trees. </li>
  <li>The number of triplets that are unresolved in both trees. </li>
  <li>The normalized number of triplets that are unresolved in
  both trees. </li>
</ul>
</p>

<h3><a id="pairs_quartet_dist">pairs_quartet_dist</a></h3>
<p>Usage: <code>bin/pairs_quartet_dist [-v] &lt;filename1&gt; &lt;filename2&gt; [&lt;output filename&gt;]</code></p>

<p> Where: <code>&lt;filename1&gt;</code> and
<code>&lt;filename2&gt;</code> point to two files each containing the
same number of trees in Newick format. The two trees on line <i>i</i> in the
two files must have the same set of leaf labels.  The output is a list
of numbers, where the <i>i</i>'th number is the quartet distance between the
two trees on line <i>i</i> in the two files. If <code>[output filename]</code> is
specified the output is written to the file pointed to (if the file
already exists the current content is deleted first), otherwise the
output is written to stdout.
</p>

<p>If the <code>-v</code> option is used, the following numbers will be reported for
each pair of trees (in this order):
<ul>
  <li>The number of leaves in the trees (should be the same for both).</li>
  <li>The number of quartets in the two trees (n choose 4). </li>
  <li>The quartet distance between the two trees. </li>
  <li>The normalized quartet distance between the two trees. </li>
  <li>The number of resolved quartets that agree in the two trees. </li>
  <li>The normalized number of resolved quartets that agree in the two trees. </li>
  <li>The number of quartets that are unresolved in both trees. </li>
  <li>The normalized number of quartets that are unresolved in
  both trees. </li>
</ul>
</p>

<h3><a id="all_pairs_triplet_dist">all_pairs_triplet_dist</a></h3>

<p>Usage: <code>all_pairs_triplet_dist &lt;input filename&gt; [output filename]</code></p>

<p>Where: <code>&lt;input filename&gt;</code> is the name of a file
containing multiple trees in Newick format. Each tree should be on a
seperate line. In each tree all leaves should be labeled and all trees
should have the same set of leaf labels.  If <code>[output filename]</code> is
specified the output is written to the file pointed to (if the file
already exists the current content is deleted first), otherwise the
output is written to stdout.  The output is a lower triangular matrix
in which the <i>i</i>, <i>j</i>'th entry is the pairwise triplet distance between
the tree on line <i>i</i> and the tree on line <i>j</i> in <code>&lt;input
filename&gt;</code>.</p>

<h3><a id="all_pairs_quartet_dist">all_pairt_quartet_dist</a></h3>

<p>Usage:  <code>all_pairs_quartet_dist &lt;input filename&gt; [output filename]</code></p>

<p>Where: <code>&lt;input filename&gt;</code> is the name of a file
containing multiple trees in Newick format. Each tree should
be on a seperate line. In each tree all leaves should be
labeled and all trees should have the same set of leaf labels.
If <code>[output filename]</code> is specified the output is written to the
file pointed to (if the file already exists the current
content is deleted first), otherwise the output is written to
stdout.  The output is a lower triangular matrix in which the
<i>i</i>, <i>j</i>'th entry is the pairwise quartet distance between the
tree on line <i>i</i> and the tree on line <i>j</i> in <code>&lt;input
filename&gt;</code>.</p>

<h2><a id="File format">File format</a></h2>

<p>All input files for tqDist should contain trees encoded in Newick
format. Here is couple of examples that can be used with the
<code>quartet_distance</code> and <code>triplet_distance</code>
executables:
</p>
<ul>
  <li><a href="files/example/trees/tree1.new">tree1.new</a></li>
  <li><a href="files/example/trees/tree2.new">tree2.new</a></li>
</ul>
<p>
And here is an example of a file containing multiple trees, which can
be used with the <code>all_pairs_quartet_distance</code>,
<code>all_pairs_triplet_distance</code>,
<code>pairs_triplet_distance</code> and
<code>pairs_triplet_distance</code>
executables:
</p>
<ul>
  <li><a href="files/example/trees/8trees.new">8trees.new</a></li>
</ul>

<p>
For details on how to encode trees in Newick format please see <a
 href="http://en.wikipedia.org/wiki/Newick_format"
target="blank">http://en.wikipedia.org/wiki/Newick_format</a>.
</p>

<h2><a id="literature">Literature</a></h2>

<p>The algorithms implemented in <code>tqDist</code> was developed by <a
href="http://birc.au.dk/~asand" target="blank">Andreas
Sand</a>, <a href="http://cs.au.dk/~gerth" target="blank">Gerth
St&oslash;lting Brodal</a>, <a href="http://www.imada.sdu.dk/~rolf/"
target="blank">Rolf Fagerberg</a>, <a
href="http://birc.au.dk/~mailund" target="blank">Thomas Mailund</a>, <a
href="http://birc.au.dk/~cstorm" target="blank">Christian
N. S. Pedersen</a>, Jens Johansen and Morten K. Holt, and they are
explained in the following two papers:

<ul>

  <li><a
   href="http://knowledgecenter.siam.org/0236-000098/0236-000098/1"
  target="blank">Efficient Algorithms for Computing the Triplet and
  Quartet Distance Between Trees of Arbitrary Degree</a>, Gerth
  St&oslash;lting Brodal, Rolf Fagerberg, Christian
  N.S. Pedersen,<br/> Thomas Mailund and Andreas Sand, Proc. 24th
  Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1814-1832,
  2013.</li>

  <li><a href="http://www.mdpi.com/2079-7737/2/4/1189"
  target="blank">Algorithms for Computing the Triplet and Quartet
  Distances for Binary and General Trees</a>, Andreas Sand, Morten
  K. Holt, Jens Johansen, Rolf Fagerberg, Gerth St&oslash;lting
  Brodal,<br/> Christian N. S. Pedersen and Thomas Mailund, Biology,
  2013, 2(4), 1189-1209</li>

</ul>
</p>

<p>The implementation is desribed in:

<ul>

  <li><i><a href="http://www.madalgo.au.dk/~gerth/pub/alenex14.html"
   target="blank">On the Scalability of Computing Triplet and Quartet
   Distances</a></i>, Morten K. Holt, Jens Johansen and Gerth
   St&oslash;lting Brodal, to appear at ALENEX 2014.</li>
    
</ul>
</p>
  
<h2><a id="contact">Contact</a></h2>

<p>If you encounter any problems or have questions about using
 <code>tqDist</code>, please contact <a
  href="mailto:cstorm@birc.au.dk">Christian N. S. Pedersen</a>.</p>

</div>
</div>
</body>
</html>
  
